package org.hw.algorithm.searchUtil;

import org.hw.algorithm.treeutil.TreeNode;

import java.util.Arrays;

public class SearchFactory{


    public static void main(String[] args) {
        int[] arr = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};
        int target = 47;

        int index = binarySearch(arr, target);
//        int index = interpolationSearch(arr, target);

        if (index != -1) {
            System.out.println("元素 " + target + " 在数组中的索引为 " + index);
        } else {
            System.out.println("元素 " + target + " 在数组中未找到");
        }
    }
    /**
     * 二分查找（前提是数组有序）
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int mid;
        // 循环条件是左边下标<=右边下标
        while (left <= right) {
            //  获取中间下标
            mid = left + (right-left) / 2;
            if (target == arr[mid]) return mid;
            else if (target > arr[mid]) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    /**
     * 插值查找（改进的二分查找，调整了插值 pos 计算方式）
     */
    public static int interpolationSearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int pos;
        while (left <= right &&   target >= arr[left] &&  target <= arr[right]) {
            if (left == right) {
                if (arr[left] == target) return left;
                return -1;
            }
            // 计算插值点
            pos = left + ((right - left) / (arr[right] - arr[left])) * (target - arr[left]);
            // 检查插值点位置是否合适
            if (target == arr[pos]) return pos;
            else if (target > arr[pos]) left = pos + 1;
            else right = pos - 1;
        }
        return -1; // 没有找到目标元素
    }

    // 获取足够长的斐波那契数列数组
    public static int[] generateFibonacci(int maxSize) {
        int[] fibonacci = new int[maxSize];
        fibonacci[0] = 1;
        fibonacci[1] = 1;

        for (int i = 2; i < fibonacci.length; i++) {
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }
        return fibonacci;
    }

    // 核心斐波那契查找
    public static int fibonacciSearch(int[] arr, int target) {
        int n = arr.length;
        // 获取与数组长度相应的斐波那契分割点下标
        int fibIndex = 0;
        int[] fibonacci = generateFibonacci(n);
        while (fibonacci[fibIndex] < n) {
            fibIndex++;
        }
        // 扩展数组以适应斐波那契数列的长度，填充最高值
        int[] temp = Arrays.copyOf(arr, fibonacci[fibIndex]);
        for (int i = n; i < temp.length; i++) {
            temp[i] = arr[n - 1];
        }

        int left = 0;
        int right = n - 1;
        while (left <= right) {
            int offset = fibonacci[fibIndex - 1] - 1;
            int mid = left + offset;

            if (target > temp[mid]) {
                left = mid + 1;
                fibIndex -= 2; // 减去的是斐波那契数列中较大的一项
            } else if (target < temp[mid]) {
                right = mid - 1;
                fibIndex -= 1; // 减去的是斐波那契数列中较小的一项
            } else {
                // 找到目标值，但要考虑实际数组长度
                if (mid < n) {
                    return mid;
                } else {
                    return right; // 因为是在扩展后的数组中找到的，实际下标应为right
                }
            }
        }
        return -1; // 没有找到目标值
    }

//    二叉排序数树查找
    public static boolean searchBST(TreeNode root, int x){
        if (root==null) return false;
        if (x==root.data){
            return true;
        }else if (x > root.data){
            return searchBST(root.right,x);
        }else {
            return searchBST(root.left,x);
        }
    }
}
